/**
 * @file backtracking.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-15
 * 
 * @copyright Copyright (c) 2021
 * 
 * 38.字符串的排列 -- 全排列II 需要去重
 * 34.二叉树中和为target的路径 -- 路径总和II
 * 12.矩阵中的路径 -- 单词搜索 -- 太jb难了！
 * 13.机器人的运动范围 -- 脑瓜子嗡嗡的
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// #define TEST34

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}
#ifndef TEST34
class Solution
{
public:
    // 38.
    vector<string> permutation(string s)
    {
        // 字符串可能重复
        std::sort(s.begin(), s.end());
        vector<string> res;
        string path;
        vector<bool> used(s.size(), false);
        backtracking38(s, res, path, used);
        return res;
    }

private:
    void backtracking38(string &s, vector<string> &res, string &path, vector<bool> &used)
    {
        if (path.size() == s.size()) {
            res.emplace_back(path);
            return;
        }
        for (int i = 0; i < s.size(); ++i) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && s[i] == s[i - 1] && used[i - 1] == false) {
                continue;
            }
            used[i] = true;
            path.push_back(s[i]);
            backtracking38(s, res, path, used);
            used[i] = false;
            path.pop_back();
        }
    }

public:
    // 12. 单词搜索
    bool exist(vector<vector<char>> &board, string word)
    {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> used(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (backtracking12(board, word, i, j, 0, used)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    bool backtracking12(vector<vector<char>> &board, string &word, int i, int j, int k, vector<vector<bool>> &used)
    {
        // 越界
        // 剪枝：board[i][j]!=word[k] || used[i][j]=true
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
            return false;
        }
        if (board[i][j] != word[k] || used[i][j]) {
            return false;
        }
        if (k == word.size() - 1) {
            return true;
        }
        used[i][j] = true;
        bool res = backtracking12(board, word, i + 1, j, k + 1, used) ||
                   backtracking12(board, word, i - 1, j, k + 1, used) ||
                   backtracking12(board, word, i, j + 1, k + 1, used) ||
                   backtracking12(board, word, i, j - 1, k + 1, used);
        used[i][j] = false; // 回溯
        return res;
    }

public:
    // 13. 机器人的运动范围
    int movingCount(int m, int n, int k)
    {
        vector<vector<bool>> used(m, vector<bool>(n, false));
        return dfs(0, 0, used, m, n, k);
    }

private:
    // 计算 x 的数位之和
    int getSum(int x)
    {
        int sum = 0;
        while (x) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    int dfs(int i, int j, vector<vector<bool>> &used, int m, int n, int k)
    {
        if (i >= m || j >= n) { // 越界
            return 0;
        }
        if (k < getSum(i) + getSum(j) || used[i][j]) { // 不可达或访问过
            return 0;
        }
        used[i][j] = true;
        return 1 + dfs(i + 1, j, used, m, n, k) + dfs(i, j + 1, used, m, n, k);
    }
};
#else

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

class Solution
{
    vector<vector<int>> res;
    vector<int> path;
    int sum = 0;

public:
    // 回溯解法一
    vector<vector<int>> pathSum(TreeNode *root, int target)
    {
        // 根节点到叶子节点的和 == target
        traversal(root, target);
        return res;
    }

private:
    void traversal(TreeNode *root, int target)
    {
        if (root == nullptr) {
            return;
        }
        sum += root->val;
        path.push_back(root->val);
        traversal(root->left, target);
        traversal(root->right, target);
        if (root->left == nullptr && root->right == nullptr && sum == target) {
            res.emplace_back(path);
        }
        sum -= root->val;
        path.pop_back();
    }
};
class Solution
{
    vector<vector<int>> res;
    vector<int> path;
    int sum = 0;

public:
    // 回溯解法二
    vector<vector<int>> pathSum(TreeNode *root, int target)
    {
        // 根节点到叶子节点的和 == target
        if (root == nullptr) {
            return res;
        }
        sum += root->val;
        path.push_back(root->val);
        traversal(root, target);
        return res;
    }

private:
    void traversal(TreeNode *root, int target)
    {
        if (root->left == nullptr && root->right == nullptr) {
            if (sum == target) {
                res.emplace_back(path);
            }
            return;
        }
        if (root->left) {
            sum += root->left->val;
            path.push_back(root->left->val);
            traversal(root->left, target);
            sum -= root->left->val;
            path.pop_back();
        }
        if (root->right) {
            sum += root->right->val;
            path.push_back(root->right->val);
            traversal(root->right, target);
            sum -= root->right->val;
            path.pop_back();
        }
    }
};
#endif
Solution solve = Solution();

#ifndef TEST34
void test38()
{
    // string s = "abc";
    string s = "aab";
    print(solve.permutation(s));
}
#endif

int main()
{
    // test38();
    return 0;
}